Regular saturated graphs and sum-free sets

In a recent paper, Gerbner, Patkós, Tuza and Vizer studied regular F-saturated graphs. One of the essential questions is given F, for which n does a regular n-vertex F-saturated graph exist. They proved that for all sufficiently large n, there is a regular $K_3$-saturated graph with n vertices. We extend this result to both $K_4$ and $K_5$ and prove some partial results for larger complete graphs. Using a variation of sum-free sets from additive combinatorics, we prove that for all $k\ge 2$, there is a regular $C_{2k+1}$-saturated with n vertices for infinitely many n. Studying the sum-free sets that give rise to $C_{2k+1}$-saturated graphs is an interesting problem on its own and we state an open problem in this direction.     

On weighted spectral radius of unraveled balls and normalized Laplacian eigenvalues

For a graph G, the unraveled ball of radius r centered at a vertex v is the ball of radius r centered at v in the universal cover of G. We obtain a lower bound on the weighted spectral radius of unraveled balls of fixed radius in a graph with positive weights on edges, which is used to present an upper bound on the $s^{\text{th}}$ (where $s\ge 2$) smallest normalized Laplacian eigenvalue of irregular graphs under minor assumptions. Moreover, when $s=2$, the result may be regarded as an Alon–Boppana type bound for a class of irregular graphs.     

Existential monadic second order logic of undirected graphs: The Le Bars conjecture is false

In 2001, J.-M. Le Bars disproved the zero-one law (that says that every sentence from a certain logic is either true asymptotically almost surely (a.a.s.), or false a.a.s.) for existential monadic second order sentences (EMSO) on undirected graphs. He proved that there exists an EMSO sentence ? such that $\mathsf{P}(G_n??)$ does not converge as $n\to \infty$ (here, the probability distribution is uniform over the set of all graphs on the labeled set of vertices $\{1,\dots ,n\}$). In the same paper, he conjectured that, for EMSO sentences with 2 first order variables, the zero-one law holds. In this paper, we disprove this conjecture.     

Highly edge-connected factors using given lists on degrees

Let G be a 2k-edge-connected graph with and let for every . A spanning subgraph F of G is called an L-factor, if for every . In this article, we show that if for every , then G has a k-edge-connected L-factor. We also show that if and for every , then G has a k-edge-connected L-factor.     

Linearly χ-bounding (P6, C4)-free graphs*

Given two graphs and , a graph is -free if it contains no induced subgraph isomorphic to or . Let and be the path on vertices and the cycle on vertices, respectively. In this paper we show that for any -free graph it holds that , where and are the chromatic number and clique number of , respectively. Our bound is attained by several graphs, for instance, the 5-cycle, the Petersen graph, the Petersen graph with an additional universal vertex, and all -critical -free graphs other than (see Hell and Huang [Discrete Appl. Math. 216 (2017), pp. 211–232]). The new result unifies previously known results on the existence of linear -binding functions for several graph classes. Our proof is based on a novel structure theorem on -free graphs that do not contain clique cutsets. Using this structure theorem we also design a polynomial time -approximation algorithm for coloring -free graphs. Our algorithm computes a coloring with colors for any -free graph in time.     

On the threshold problem for Latin boxes

Let m ≤ n ≤ k. An m × n × k 0‐1 array is a Latin box if it contains exactly m n ones, and has at most one 1 in each line. As a special case, Latin boxes in which m = n = k are equivalent to Latin squares. Let be the distribution on m × n × k 0‐1 arrays where each entry is 1 with probability p, independently of the other entries. The threshold question for Latin squares asks when contains a Latin square with high probability. More generally, when does support a Latin box with high probability? Let ε > 0. We give an asymptotically tight answer to this question in the special cases where n = k and , and where n = m and . In both cases, the threshold probability is . This implies threshold results for Latin rectangles and proper edge‐colorings of K_n,n.